/**
    ******************************************************************************
    * @file    stack.c
    * @author  debian
    * @version V1.0.0
    * @date    2019-11-30
    * @brief   栈
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "stack.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup stack
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup stack_Exported_Functions stack Exported Functions
    * @{
    */

/** @defgroup stack_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the stack
        to be ready for use.
 
@endverbatim
    * @{
    */ 

/**
    * @brief  创建stack对象
    * @param  
    * @retval 
    */ 
    int stack_creat(struct Stack *s, int size)
    {
		if(s == NULL)
			return -1;

		s->data = (Elemtype *)calloc(size, sizeof(Elemtype));
		if(s->data == NULL)
			return -2;

		s->size = size;
		s->top = 0;
		
        return 0;
    }

/**
    * @brief  销毁stack对象
    * @param  
    * @retval 
    */ 
    int stack_destroy(struct Stack *s)
    {
		if(s->data)
			free(s->data);
		return 0;
    }

	
/**
    * @}
    */

/** @defgroup stack_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the stack.

@endverbatim
    * @{
    */

        /* 操作函数写在这里 */
/**
    * @brief  入栈,内部支持扩容
    * @param  
    * @retval 
    */ 
    int stack_push(struct Stack *s, Elemtype data)
    {
		if(s == NULL)
			return -1;

		if(s->top >= s->size)   //这个是要等于，因为有0
		{
			int new_len = (s->size>>1) + s->size;
			//printf("len = %d %d %d\n", s->size>>1, s->size, new_len);
			s->data = realloc(s->data, new_len*sizeof(Elemtype));   	//扩容1.5倍,realloc可以复制之前数据到新的内容区
			if(s == NULL)
				return -2;

			s->size = new_len;
		}

		s->data[s->top] = data;
		s->top++;
		
        return 0;
    }


/**
	* @brief  出栈，
	* @param  
	* @retval 
	*/ 
	int stack_pop(struct Stack *s, Elemtype *data)
	{
		if(s == NULL || data == NULL)
			return -1;

		//可以做减少容量的操作
		
		if(s->top == 0)
			return -2;

		*data = s->data[--s->top];    //这个是指向栈顶的，需要先减
		return 0;
	}

	
	/**
		* @brief  获取栈的栈顶元素，不出栈
		* @param  
		* @retval 
		*/ 
		int stack_top(struct Stack *s, Elemtype *data)
		{
			if(s == NULL || data == NULL)
				return -1;
	
			//可以做减少容量的操作
			
			if(s->top == 0)
				return -2;
			int top = s->top - 1;
			*data = s->data[top];	  //这个是指向栈顶的，需要先减
			return 0;
		}

/**
	* @brief  栈的长度
	* @param  
	* @retval 
	*/ 
	int stack_len(struct Stack *s)
	{
		if(s == NULL)
			return -1;
		return s->top;
	}



/**
	* @brief  遍历栈
	* @param  
	* @retval 
	*/ 
	int stack_bainli(struct Stack *s)
	{
		if(s == NULL)
			return -1;

		int i = s->size;

		printf("stack bainli %d %d\n", s->top, s->size);
		for(i=0;i<s->top;i++)
		{
			printf("%d ", s->data[i]);
		}
		printf("\n");

		return 0;
	}


	/********************************/
	/******* 面试中算法 *************/
	/********************************/	

	/**
	* @brief  有效括号
	* @param  s: 字符串
	* @retval 
	*/ 
	int stack_ValidParentheses(char *s)
	{
		//1.创建一个栈
		struct Stack st;
		stack_creat(&st, 10);

		//2.分解字符串，c语言只能用指针遍历
		char *c = s;
		while(*c != '\0')
		{
			//3.判断是否是左括号，是的话就入栈,否则取出栈顶元素做判断
			if(*c == '(' || *c == '[' || *c == '{')
			{
				stack_push(&st, *c);
			}
			else
			{
				int cc;
				//先做检测，如果栈为空，返回失败
				if(stack_len(&st) == 0)
					return -1;
				stack_pop(&st, &cc);
				
				//判断是否跟输入的一致
				if(*c == ')' && cc != '(' ||
					*c == ']' && cc != '[' ||
					*c == '}' && cc != '{' )
				{
					return -1;
				}
			}
			c++;
		}

		//4.如果栈为空，就说明匹配成功，反则失败
		if(stack_len(&st) == 0)
			return 0;
		return -1;
	}


	/**
	* @brief  最小栈创建
	* @param  
	* @retval 
	*/ 
	static struct Stack gs_stA;
	static struct Stack gs_stB;
	int stackMin_init(void)
	{
		//1.创建一个栈A
		stack_creat(&gs_stA, 10);
		stack_creat(&gs_stB, 10);
		
		return 0;
	}

	int stackMin_push(Elemtype data)
	{
		//1.入栈
		Elemtype temp;
		
		//判断栈B是否为空，为空直接进栈
		if(stack_len(&gs_stB) == 0)
		{
			stack_push(&gs_stB, data);
		}
		else
		{
			//跟栈顶元素判断，如果小于栈顶元素进栈
			stack_top(&gs_stB, &temp);
			if(data <= temp)
			{
				stack_push(&gs_stB, data);
			}
		}

		//栈A都需要进栈
		stack_push(&gs_stA, data);
		
		return 0;
	}

	Elemtype stackMin_pop(void)
	{
		//1.出栈
		Elemtype tempA, tempB;

		//栈A先出栈
		stack_pop(&gs_stA, &tempA);


		//看看栈B的栈顶元素
		if(stack_len(&gs_stB) != 0)
		{
			stack_top(&gs_stB, &tempB);
			if(tempA == tempB)
				stack_pop(&gs_stB, &tempB);	
		}
		
		return 0;
	}

	Elemtype stackMin_top(void)
	{
		//1.出栈
		Elemtype tempA;

		//栈A先出栈
		stack_top(&gs_stA, &tempA);
		
		return tempA;
	}

	Elemtype stackMin_getMin(void)
	{
		//最小值
		Elemtype temp;
		
		//判断栈B是否为空，不为空直接获取最小值
		if(stack_len(&gs_stB) != 0)
		{
			stack_top(&gs_stB, &temp);
			return temp;
		}
		
		return -1;
	}




	#if 1
	int main()
	{
	    int i = 0;
		int ret = -1;

		struct Stack s;
		int a = -1;
		
		stack_creat(&s, 2);

		stack_push(&s, 2);
		stack_push(&s, 5);
		stack_push(&s, 6);
		stack_push(&s, 9);
		stack_push(&s, 11);

		stack_bainli(&s);

		stack_pop(&s, &a);
		printf("aaa = %d\n", a);
		stack_bainli(&s);
		
		printf("有效栈 %d\n", stack_ValidParentheses("[]{}("));

		//最小栈
		stackMin_init();
		stackMin_push(-2);
		stackMin_push(0);
		stackMin_push(-3);
		printf("最小值 %d\n", stackMin_getMin());
		stackMin_pop();
		printf("top %d\n", stackMin_top());
		printf("最小值 %d\n", stackMin_getMin());
		
		
	    return 0;

	}
	#endif

    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2019 HOME 深圳龙华 *****END OF FILE****/

